import utils.TreeNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/9 9:14
 * @description:
 */
public class Solution106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public TreeNode buildTree(int[] inorder, int inorderLeft, int inorderRight, int[] postorder, int postorderLeft, int postorderRight) {
        if (inorderLeft <= inorderRight && postorderLeft <= postorderRight) {
            TreeNode root = new TreeNode(postorder[postorderRight]);
            int leftLen = 0;
            for (int i = inorderLeft; i <= inorderRight; i++) {
                if (inorder[i] != root.val) {
                    leftLen++;
                }else{
                    break;
                }
            }
            int rightLen = inorderRight - inorderLeft + 1 - 1 - leftLen;
            root.right = buildTree(inorder, inorderRight - rightLen + 1, inorderRight, postorder, postorderRight - rightLen, postorderRight - 1);
            root.left = buildTree(inorder, inorderLeft, inorderLeft + leftLen - 1, postorder, postorderLeft, postorderLeft + leftLen - 1);
            return root;
        }
        return null;
    }

    public static void main(String[] args) {
        Solution106 solution = new Solution106();
        TreeNode root = solution.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        TreeNode.show(root);
    }
}
